/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-08-18
 * Time: 15:27
 * To BE A Better Person-2020-3-2
 */
class BinarySearchTree{
    static class Node {
        public int key;
        public Node left;
        public Node right;

        public Node(int key) {
            this.key = key;
        }



    }
    public Node root;
    public boolean insert(int key){
        //没有插入任何元素
        if(root == null){
            root = new Node(key);
            return true;
        }

        Node parent=null;
        Node cur=root;

        //找到位置
        while(cur != null){
            if(key < cur.key){
                parent=cur;
                cur=cur.left;
            }else if(key > cur.key){
                parent=cur;
                cur=cur.right;
            }else{
                return false;
            }
        }
        Node temp=new Node(key);
        //开始插入
        if(parent.key>key){
            parent.left=temp;
        }else {
            parent.right=temp;
        }
        return true;
    }

    public boolean Search(int key){
        if(root == null) {
            throw  new NullPointerException();
        }
        Node cur=root;
        while(cur != null){
            if(key < cur.key){

                cur=cur.left;
            }else if(key > cur.key){

                cur=cur.right;
            }else{
                return true;
            }
        }
        return false;
    }

    public boolean delete(int key){
        //先找到这个点
        Node cur=root;
        Node parent=null;
        while(cur.key != key){
            if(cur.key < key){
                parent=cur;
                cur=cur.right;
            }else {
                parent=cur;
                cur=cur.left;
            }
            if (cur == null){
                return false;
            }
        }

        if(cur.left == null){
            if(cur == root){
                root= cur.right;
            }else if(parent.right == cur){
                parent.right=cur.right;
            }else if(parent.left == cur){
                parent.left=cur.right;
            }
        }else if (cur.right == null){
            if(cur == root){
                root= cur.left;
            }else if(parent.right == cur){
                parent.right=cur.left;
            }else if(parent.left == cur){
                parent.left=cur.left;
            }
        }else{
            //右边找最小
            Node temp=cur;
            Node temp_parent=parent;
            while(temp.left != null){
                temp_parent=temp;
                temp=temp.left;
            }
            cur.key=temp.key;
            parent.left=cur.right;

        }
        return true;
    }
}

public class TestDemo {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree=new BinarySearchTree();

        int[] arr={10,20,3,56,78,23,5,1};
        for (int i = 0; i < arr.length; i++) {
            binarySearchTree.insert(arr[i]);
        }

        System.out.println(binarySearchTree.Search(5));
        binarySearchTree.delete(56);
        System.out.println("asdas");
    }
}
